package shuanfa.graph;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

public class GraphTraversal {
    Graph graph;
    boolean[] visited;//用以标记节点是否被访问

    public GraphTraversal(Graph graph) {
        this.graph = graph;
        visited = new boolean[graph.graphs.size()];
    }

    public static void main(String[] args) {
        GraphTraversal graphTraversal = new GraphTraversal(new Graph(4));
        graphTraversal.DFS();
    }

    public void DFS() {
        for (int i = 0; i < graph.graphs.size(); i++) {
            if (!visited[i]) {//未被访问
                DFSTraversal(i);
            }
        }
    }

    private void DFSTraversal(int v) {
        if (visited[v]) return;
        visited[v] = true;
        System.out.println(v + "->");
        Iterator<Integer> integerListIterator = graph.graphs.get(v).listIterator();
        while (integerListIterator.hasNext()) {
            int nextNode = integerListIterator.next();
            if (!visited[nextNode]) {
                DFSTraversal(nextNode);//若该节点未被访问，递归继续深度遍历
            }
        }
    }

    public void BFS() {
        for (int i = 0; i < graph.graphs.size(); i++) {
            if (!visited[i]) {//未被访问
                BFSTraversal(i);
            }
        }
    }

    private void BFSTraversal(int v) {
        if (visited[v]) return;
        visited[v] = true;
        Deque<Integer> queue = new ArrayDeque<>(visited.length);
        queue.offerFirst(v);
        System.out.println(v + "->");
        while (queue.size() != 0) {
            Integer cur = queue.pollFirst();
            System.out.println(cur + "->");
            Iterator<Integer> iterator = graph.graphs.get(cur).listIterator();
            while (iterator.hasNext()) {
                int nextNode = iterator.next();
                if (!visited[nextNode]) {
                    queue.offerLast(nextNode);
                    visited[nextNode] = true;
                }
            }
        }
    }
}
